/**

This file is part of MaCI/GIMnet.

MaCI/GIMnet is free software: you can redistribute it and/or modify it 
under the terms of the GNU Lesser General Public License as published 
by the Free Software Foundation, either version 3 of the License, or 
(at your option) any later version.

MaCI/GIMnet is distributed in the hope that it will be useful, but WITHOUT 
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public 
License for more details.

You should have received a copy of the GNU Lesser General Public 
License along with GIMnet. (See COPYING.LESSER) If not, see 
<http://www.gnu.org/licenses/>.

**/
/**
 * \file
 * \brief Backlog template class for storing / fetching data by timestamp.
 * \author Antti Maula <antti.maula@tkk.fi>
 *
 * \todo Optimize the searching function. Now it looks through
 * the whole buffer, and even starts from the oldest ones.
 */
#ifndef _ASKDJHSDFJHGWDSRFHSDFJXCVJHGSDF_DATABACKLOG_HPP_
#define _ASKDJHSDFJHGWDSRFHSDFJXCVJHGSDF_DATABACKLOG_HPP_
#include "gimutils.h"
#include <list>
#include <assert.h>

namespace gim {

  /** Type of timereference to use for clearing queue.
   */
  enum EBackLogReference {
    /// Use current system time as time reference
    KBackLogReferenceSystemTime = 1,

    /// Use the time of last added element as time reference
    KBackLogReferenceLastElement = 2 
  }; 

  /** Time keying based data backlog class.
   *
   * This class implements a data storage which can be queried based
   * on a timestamp. The class returns the data element which has the
   * closest timestamp. This is implemented as template class, so any
   * kind of data can be stored on the container.
   *
   * \note This class works fine with elementcounts < 1000. Bigger
   * numbers start to get slow. Fixing this would need a change on the
   * FindNearestEntry function, which is now stupidly iterating
   * through all elements in sequence while searching.
   */
  template <typename T>
  class CDataBacklog
  {
  public:
    /** Class constructor.
     *
     * @param[in] aBacklogLength_ms Maximum age in milliseconds to
     * keep data. This doesn't limit the _number_ of data elements,
     * but rather their age. For example; store position information
     * from the last 5 seconds. If this parameter is set to 0, the
     * array is not automatically cleared. (You must manually call
     * some of the Clear() function family in case this is required)
     * This limit is relative, and all operations are calculated against
     * the current system time.
     * @param[in] aBacklogLength_MaxCount Absolute maximum limit of
     * log elementcount. If this is set to 0, the log is limited by
     * only the time. This limits acts as a safety limit for
     * applications where the time may not be working correctly (or
     * linearly). Note that once set; this parameter is always obeyed,
     * the Clear() selector on PushData() function does not affect
     * this limit.
     * @param[in] aReference Select used time reference. See type
     * EBackLogReference for more info.
     *
     * \see Clear(const unsigned int)
     * \see PushData(const gim::time, const T &, const bool)
     * \see EBackLogReference
     */
    CDataBacklog(const unsigned int aBacklogLength_ms,
                 const unsigned int aBacklogLength_MaxCount = 0,
                 EBackLogReference aReference = KBackLogReferenceSystemTime);


    /** Destructor.
     *
     * This functions takes care of destructing the DataBacklog
     * container.
     */
    ~CDataBacklog();


    /** Push new element to Backlog.
     *
     * This functions pushes a new element to the end of the element
     * array. 
     *
     * \note This function assumes that the data elements are in
     * chronological order, and processes the Peek/Pop requests
     * according to this assumption. If you require support for
     * inserting random ordered elements, contact module author.
     *
     * @param[in] aTimestamp    Timestamp to set for the new element.
     * @param[in] aData         Data element to store.
     * @param[in] aCleanBacklog Flag indicating whether the Clear()
     *                          function should be called after Push.
     */
    void PushData(const gim::time &aTimestamp, const T &aData, const bool aCleanBacklog = true);


    /** Pop element from Backlog.
     *
     * This function looks for the closest matching timestamp from the
     * array of stored data elements. Selected element is stored on
     * the provided reference and removed from the backlog. (== Pop).
     *
     * @param[out] aData        Reference to object for storing the data.
     * @param[in] aTimestamp    Timestamp to look for.
     * @param[out] aDiff        Pointer to time object. If this is set
     *                          to non-NULL, after a succesfull call it will
     *                          contain the time difference between the requested
     *                          time and selected element.
     * @return                  'true' when element was selected and copied. 'false'
     *                          when the backlog is empty (no elements to copy)
     */
    bool PopData(T &aData, const gim::time &aTimestamp, gim::time *aDiff = NULL);


    /** Peek element from Backlog.
     *
     * This function looks for the closest matching timestamp from the
     * array of stored data elements. Selected element is stored on
     * the provided reference. The backlog is not modified during the
     * call.
     *
     * @param[out] aData        Reference to object for storing the data.
     * @param[in] aTimestamp    Timestamp to look for.
     * @param[out] aDiff        Pointer to time object. If this is set
     *                          to non-NULL, after a succesfull call it will
     *                          contain the time difference between the requested
     *                          time and selected element.
     * @return                  'true' when element was selected and copied. 'false'
     *                          when the backlog is empty (no elements to copy)
     */
    bool PeekData(T &aData, const gim::time &aTimestamp, gim::time *aDiff = NULL);


    /** Clear the backlog.
     *
     * Removes all existing entries from the backlog.
     */
    void Clear(void);


    /** Clear entries older than specified relative age from backlog.
     *
     * Removes all existing entries from backlog which are older than
     * the specified time limit. The reference time for this function
     * is the current system time as reported by the
     * ownTime_GetTimeOfDay() function. If you are using synthetised
     * time, consider using the absolute version: \n Clear(const
     * gim::time &) instead.
     *
     * @param[in] aAgeLimit_ms  Relative time in milliseconds to use
     *                          as a limit when clearing old entries.
     */
    void Clear(const unsigned int aAgeLimit_ms);


    /** Clear entries older than specified absolute age from backlog.
     *
     * Removes all existing entries from backlog which are older than
     * the specified absolute time limit. The function works so that
     * is removes all entries which are compared to be smaller than
     * the given parameter.
     *
     * @param[in] aAgeAbsoluteLimit Absolute limit to use for clearing.
     *                              All entries which are older 
     *                              (smaller) than this are removed.
     */
    void Clear(const gim::time &aAgeAbsoluteLimit);


    /** Return number of entries currently in backlog.
     *
     * @return                  Number of elements in the backlog container.
     */
    inline unsigned int GetBacklogCount(void) const;


  private:
    /// Type for a single Backlog entry.
    typedef typename std::pair < gim::time, T > TDataBacklogEntry;

    /// Type for a std::list<> of TDataBacklogEntry entries.
    typedef typename std::list< TDataBacklogEntry > TDataBacklogEntryArray;

    /// Type for iterator of std::list<> of TDataBacklogEntry entries.
    typedef typename TDataBacklogEntryArray::iterator TDataBacklogEntryArrayIterator;

    // Variables
    unsigned int iBacklogLength_ms; ///< Length limit of backlog.
    unsigned int iBacklogLength_MaxCount; ///< Maximum number of elements in queue.
    EBackLogReference iBacklogReference; ///< Backlog reference.
    TDataBacklogEntryArray iDataBacklog; ///< Datacontainer of backlog.
    
    /// Return iterator based on closest timestamp. If empty; returns container.end():
    TDataBacklogEntryArrayIterator FindNearestEntry(const gim::time &aTimestamp);
  };

  /////////////////////////////////////////////////////////////////////////////
  /////////////////////////////////////////////////////////////////////////////
  /////////////////////////////////////////////////////////////////////////////
  /////////////////////////////////////////////////////////////////////////////
  /////////////////////////////////////////////////////////////////////////////
  /////////////////////////////////////////////////////////////////////////////
  /////////////////////////////////////////////////////////////////////////////
  /////////////////////////////////////////////////////////////////////////////
  /////////////////////////////////////////////////////////////////////////////
  /////////////////////////////////////////////////////////////////////////////
  /////////////////////////////////////////////////////////////////////////////
  /////// Implementation //////////////////////////////////////////////////////
  /////////////////////////////////////////////////////////////////////////////
  /////////////////////////////////////////////////////////////////////////////
  /////////////////////////////////////////////////////////////////////////////
  /////////////////////////////////////////////////////////////////////////////
  /////////////////////////////////////////////////////////////////////////////
  /////////////////////////////////////////////////////////////////////////////
  /////////////////////////////////////////////////////////////////////////////
  /////////////////////////////////////////////////////////////////////////////
  /////////////////////////////////////////////////////////////////////////////
  /////////////////////////////////////////////////////////////////////////////
  /////////////////////////////////////////////////////////////////////////////

  template <typename T> 
  CDataBacklog<T>::CDataBacklog(const unsigned int aBacklogLength_ms,
                                const unsigned int aBacklogLength_MaxCount,
                                EBackLogReference aReference)
    : iBacklogLength_ms(aBacklogLength_ms),
      iBacklogLength_MaxCount(aBacklogLength_MaxCount),
      iBacklogReference(aReference),
      iDataBacklog()
  {
  }
  //*****************************************************************************
  
  template <typename T> 
  CDataBacklog<T>::~CDataBacklog()
  {
    iDataBacklog.clear();
  }
  //*****************************************************************************

  template <typename T> 
  void CDataBacklog<T>::PushData(const gim::time &aTimestamp, const T &aData, 
                                 const bool iCleanBacklog)
  {
    if (!iDataBacklog.empty() && aTimestamp < iDataBacklog.back().first) {
      dPrint(ODWARN,"Warning: Pushed timestamp is older than the previous! (Clearing cache)");
      iDataBacklog.clear();
    }

    iDataBacklog.push_back(TDataBacklogEntry(aTimestamp, aData));

    if (iCleanBacklog) {
      Clear(iBacklogLength_ms);
    }
    if (iBacklogLength_MaxCount) {
      if (iDataBacklog.size() > iBacklogLength_MaxCount) {
        iDataBacklog.pop_front();
      }
    }
  }
  //*****************************************************************************

  template <typename T> 
  typename CDataBacklog<T>::TDataBacklogEntryArrayIterator 
  CDataBacklog<T>::FindNearestEntry(const gim::time &aTimestamp)
  {
    TDataBacklogEntryArrayIterator i = iDataBacklog.begin();
    TDataBacklogEntryArrayIterator p = iDataBacklog.begin();
    const TDataBacklogEntryArrayIterator end = iDataBacklog.end();

    while(i != end) {
      const gim::time &t_lower = p->first;
      const gim::time &t_upper = i->first;
    
      if (aTimestamp < t_upper) {
        // Found upper limit, (t_upper > aTimestamp) If this is not
        // the first one; compare with previous
        if (i != p) {
          const gim::time abs_diff_l = aTimestamp - t_lower;
          const gim::time abs_diff_u = t_upper - aTimestamp; // Reversed to stay positive
          
          // Got differences, now decide the better.
          if (abs_diff_u < abs_diff_l) {
            // Upper limit diff to requested is smaller; store
            // current to previous before 'break;'
            p = i;
          }        
        }
        
        // Break the loop, leaving the current 'i' at correct position.
        break;
      }
      p = i; // Store previous iterator
      ++i; // Increment the main iterator.
    }

    // Return the 'previous'.
    return p;
  }
  //*****************************************************************************

  template <typename T> 
  bool CDataBacklog<T>::PopData(T &aData, 
                                const gim::time &aTimestamp, 
                                gim::time *aDiff)
  {
    bool result = false;
    TDataBacklogEntryArrayIterator i = FindNearestEntry(aTimestamp);
  
    if (i != iDataBacklog.end()) {
      // Got result
    
      // If aDiff is requested, store it here.
      if (aDiff) {
        if (aTimestamp < i->first) {
          *aDiff = i->first - aTimestamp;
        } else {
          *aDiff = aTimestamp - i->first;
        }
      }
    
      // Copy data.
      aData = i->second;
  
      // Delete entry (pop!)
      iDataBacklog.erase(i);
  
      // Set result.
      result = true;
    }
  
    return result;
  }
  //*****************************************************************************

  template <typename T> 
  bool CDataBacklog<T>::PeekData(T &aData, 
                                 const gim::time &aTimestamp,
                                 gim::time *aDiff)
  {
    bool result = false;
    TDataBacklogEntryArrayIterator i = FindNearestEntry(aTimestamp);
  
    if (i != iDataBacklog.end()) {
      // Got result
    
      // If aDiff is requested, store it here.
      if (aDiff) {
        if (aTimestamp < i->first) {
          *aDiff = i->first - aTimestamp;
        } else {
          *aDiff = aTimestamp - i->first;
        }
      }
    
      // Copy data.
      aData = i->second;

      // Set result.
      result = true;
    }
  
    return result;
  }
  //*****************************************************************************

  template <typename T> 
  void CDataBacklog<T>::Clear()
  {
    iDataBacklog.clear();
  }
  //*****************************************************************************

  template <typename T> 
  void CDataBacklog<T>::Clear(const unsigned int aAgeLimit_ms)
  {
    // Time element.
    gim::time limit;
    
    if (iBacklogReference == KBackLogReferenceSystemTime) {
      // Selected mode is SystemTime
      limit.setToCurrent();
      limit.reduceTimeMs(aAgeLimit_ms);
      
    } else if (iBacklogReference == KBackLogReferenceLastElement) {
      // Selected mode is LastEntry
      limit = iDataBacklog.back().first;
      limit.reduceTimeMs(aAgeLimit_ms);
      
    } else {
      // This will always fail if this branch is reached. But optimizes
      // not to test it at begin :)
      assert(iBacklogReference == KBackLogReferenceLastElement ||
             iBacklogReference == KBackLogReferenceSystemTime);
    }

    // Do the clear based on previously calculated value.
    Clear(limit);
  }
  //*****************************************************************************
  
  template <typename T> 
  void CDataBacklog<T>::Clear(const gim::time &aAgeAbsoluteLimit)
  {
    TDataBacklogEntryArrayIterator i = iDataBacklog.begin();
    while(i != iDataBacklog.end()) {
      const gim::time &tstamp = i->first;
      if (tstamp < aAgeAbsoluteLimit) {
        TDataBacklogEntryArrayIterator di = i; // Store 'delete ptr'
        ++i; // increment the traversing ptr
        iDataBacklog.erase(di); // delete the stored entry
      } else {
        // Entry was not older? So there will no more of them -> Exit.
        break;
      }
    }
  }
  //*****************************************************************************
  
  template <typename T> 
  inline unsigned int CDataBacklog<T>::GetBacklogCount(void) const
  {
    return iDataBacklog.size();
  } 
  //*****************************************************************************
  //*****************************************************************************
  //*****************************************************************************
}
#endif
